The rapid growth of the complexity of modern electronic circuits has forced electronic circuit designers to rely upon computer programs to assist or automate most steps of the design process. Typical circuits today contain hundreds of thousands or millions of individual pieces or “cells.” Such a design is much too large for a circuit designer or even an engineering team of designers to manage effectively manually.
One of the most difficult, complex and time-consuming tasks in the design process is known as cell placement, or more simply “placement.” The placement problem is the assignment of a collection of connected cells to positions in a 2-dimensional arena, such that objective functions such as total wire length are minimized.
Conventionally, both the X and Y coordinates of the cells are determined simultaneously. There are many well known tools commercially available to accomplish this task, for example, the “Physical Compiler” commercially available from Synopsys of Mountain View, Calif.
Modern chip design methods often involve combining both large design elements with smaller design elements. For example, a large element may be a random access memory, or RAM, which may be designed by an automated memory compiler. Other examples of large design elements include intellectual property blocks, or “IP blocks.” Such IP blocks may implement complex functions, for example a processor core or a UART, which were designed previously and made available for integration into future designs.
The smallest design element is typically a cell, which may implement a basic logic function, for example a NAND gate. Such cells may be used to integrate existing IP or memory blocks together, and/or to implement new designs.
It is not unusual for a large element to be three to six orders of magnitude larger than the smallest elements. For example, it is not uncommon for a RAM block or cell to comprise a chip area equivalent to the area of 75,000 to 100,000 individual cells.
Unfortunately, simultaneous placement of such large cells with numerous small cells has generally not been successful in prior art automatic placers. The prior art design process for a chip containing such large blocks or cells typically involves several stages of manual intervention to locate and fix in place such large cells, while removing illegal overlap conditions with many, perhaps thousands, of small cells. Such manual involvement in design processes may be described as more of an art than a science. Further, manual intervention generally lengthens the design duration, requires highly skilled people, is inconsistent and generally not as optimized as a fully automated process.
Therefore, for these reasons and more, an automatic method of removing overlap among cells is highly desired. Such a method would have wide application in almost every area of integrated circuit application, including ASICs, systems on a chip (SOC), gate arrays and more.